#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/23 19:17
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 后缀树.py
# @Software: PyCharm
from datetime import datetime
from hashlib import sha1


class SuffixTree:
    class Node:
        def __init__(self, s='', x=0):
            self.s = s
            self.children = None
            self.brother = None
            self.end = True
            self.val = x

    class Set:
        def __init__(self):
            self.m = {}

        def reset(self):
            self.m = {}

        def find(self, x):
            if self.m.get(x) is not None:
                if self.m[x] == x:
                    return x
                return self.find(self.m[x])
            else:
                self.m[x] = x
                return x

        def merge(self, x, y):
            self.m[self.find(y)] = x

    def newNode(self, s=''):
        self.n += 1
        return self.Node(s, self.n), self.n

    def __init__(self, s):
        self.s = s
        self.len = len(s)
        self.root = None
        self.n = 0
        self.m = []
        self.ques = {}
        if s:
            # self.root = self.Node(self.s)
            # self.root, k = self.newNode(self.s)
            # self.m.append(k)
            for i in range(0, self.len):
                # self.addStr(s[i:], i)
                k = self.addStr(s[i:])
                print('k:', k)
                self.m.append(self.addStr(s[i:]))
        else:
            self.root = None

    def addStr(self, s):

        def add(nd=self.root, ss=s):
            ls = len(ss)
            p = nd
            while p:
                if p.s and p.s[0] == ss[0]:
                    break
                p = p.brother
            if not p:
                # q = self.Node(ss, val)
                q, k = self.newNode(ss)
                q.brother = nd.brother
                nd.brother = q
            else:
                ii = 0
                lp = len(p.s)
                while ii < ls and ii < lp and ss[ii] == p.s[ii]:
                    ii += 1
                if ls > lp and ii >= lp:
                    if p.children:
                        k = add(p.children, ss[ii:])
                    else:
                        # q = self.Node(ss[ii:], val)
                        q, k = self.newNode(ss[ii:])
                        q.brother = p.children
                        p.children = q
                elif ls == lp and ii >= lp:
                    p.end = True
                    # p.val = val
                    k = p.val
                else:
                    # q = self.Node(p.s[ii:], p.val)
                    q, k = self.newNode(p.s[ii:])
                    q.children = p.children
                    p.children = q
                    p.s = p.s[:ii]
                    if ii < ls:
                        # r = self.Node(ss[ii:], val)
                        r, k = self.newNode(ss[ii:])
                        r.brother = p.children
                        p.children = r
                        p.end = False
                print('s:', s)
                print('k:', k)
                return k
        if not self.root:
            # self.root = self.Node(s)
            self.root, k = self.newNode(s)
        else:
            k = add()
        return k

    def addSuffix(self, s):
        ls = len(s)
        for i in range(ls):
            # self.addStr(s[i:], i+2-ls if i+2-ls <= 0 else ls-1)
            k = self.addStr(s[i:])
            print('k:', k, i)
            self.ques[self.m[ls-i-2]] = k


    def ans(self):
        ll = self.len-1
        q = {}
        for i in range(ll):
            q[i] = -i
            q[-i] = i
        ans = {}
        vis = {}
        m = self.Set()

        def work(nd=self.root):
            if not nd:
                return
            c = nd.children
            while c:
                work(c)
                m.merge(nd.val, c.val)
                if not vis.get(c.val):
                    vis[c.val] = True
            if nd.end and q.get(nd.val) is not None:
                if vis.get(q[nd.val]):
                    ans[nd.val] = m.find(q[nd.val])
        work()
        ll = {}

        def work0(nd=self.root):
            if not nd:
                return
            ll[nd.val] = len(nd.s)
            c = nd.children
            while c:
                work0(c)
                c = c.brother
        work0()
        ans = 0
        # for x in q:

    def display(self):
        def display(nd, dp=0, ss=''):
            if not nd:
                return
            if nd.brother:
                tag = '├─'
            else:
                tag = '└─'
            end = '(end)' if nd.end else ''
            pre = ss + '|' if ss else ''
            print('%s%s:%s[%d]' % ('  '*dp, tag, pre+nd.s+end, nd.val))
            c = nd.children
            while c:
                display(c, dp+1, ss+nd.s)
                c = c.brother
        p = self.root
        while p:
            display(p)
            p = p.brother


def main():
    # st = SuffixTree('acbbacb')
    # print('ok')
    # st.display()
    # print('------end-------')
    # print('start...')
    # st1 = SuffixTree('abceabd')
    # st1.display()
    # print('end..')
    s = 'abcbe$'
    ss = 'ebcba#'
    print(s)
    print(ss)
    st2 = SuffixTree(s)
    st2.display()
    st2.addSuffix(ss)
    print('----')
    st2.display()
    print('end..')
    print(st2.m)
    print(st2.ques)
    now = datetime.now()
    print(now.weekday())
    print(now.timestamp())
    string1 = '1231235kjskjfsohn123j123'
    print(string1)
    sha = sha1(string1.encode('utf-8'))
    ss = sha.hexdigest()
    print(ss)


if __name__ == '__main__':
    main()
